# 作者: 肖老师
# 2024年11月18日22时23分22秒
# xxxrlmk@163.com
class Node:
    """节点类"""

    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree(object):
    """树类"""

    def __init__(self):
        self.root = None  # 树根
        self.myQueue = []  # 辅助队列，当然deque作为双向循环链表队列，效率更高，但此此处只为演示方便

    def add(self, elem):  # 类似
        new_node = Node(elem)
        self.myQueue.append(new_node)  # 放入队列
        if self.root is None:  # 树根为空
            self.root = new_node
        else:
            if self.myQueue[0].lchild is None:  # 左孩子为空，放左孩子位置
                self.myQueue[0].lchild = new_node
            else:  # 右孩子为空，放右孩子位置
                self.myQueue[0].rchild = new_node
                self.myQueue.pop(0)  # 出队

    def pre_order(self, current_node: Node):
        if current_node:
            print(current_node.elem, end=' ')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self, current_node: Node):
        if current_node:
            self.mid_order(current_node.lchild)
            print(current_node.elem, end=' ')
            self.mid_order(current_node.rchild)

    def last_order(self, current_node: Node):
        if current_node:
            self.last_order(current_node.lchild)
            self.last_order(current_node.rchild)
            print(current_node.elem, end=' ')

    def level_order(self):
        my_queue = []
        my_queue.append(self.root)
        while my_queue:
            print(my_queue[0].elem, end=' ')
            node: Node = my_queue.pop(0)
            if node.lchild:
                my_queue.append(node.lchild)
            if node.rchild:
                my_queue.append(node.rchild)


if __name__ == '__main__':
    tree = Tree()
    for elem in range(10):
        tree.add(elem)
    tree.pre_order(tree.root)  # 前序遍历，就是深度优先遍历
    print()
    tree.mid_order(tree.root)
    print()
    tree.last_order(tree.root)
    print()
    tree.level_order()
